A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
1. Field of the Invention
This invention relates to computer-based image processing with digital halftoning, and more particularly to methods and apparatus for efficient storage and generation of digital halftoning screens by generating repeating patterns from a pattern header.
2. The Prior Art
The recent proliferation of computer-based image processing in the desk-top publishing and graphic arts industries has created a demand for output devices which accurately reproduce a wide variety of color images. Such images are typically represented as binary digital data generated and/or stored in a computer system and may originate from computer-aided drafting systems, digital scanning of photographic images, or other sources.
Many devices for rendering color patterns of digitized images are currently available in the marketplace and/or under development. Those used in the printing industry to produce "hard-copy" output employ such technologies as electrostatic (as in the Model G3048 Color Electrostatic Plotter available from Oce Graphics USA Inc. of Mountain View, Calif.), thermal transfer of ink from coated sheets (as in the Oce Graphics Model G5232 Color Thermal Plotter), dye thermal sublimation (DuPont 4CAST digital color imager), and ink jets (Hewlett-Packard Paintjet XL). Other color image rendering devices include cathode-ray tube display screens, liquid crystal display screens, apparatus for preparing images for computer memory storage (as in the Intel 82786 graphics coprocessor), and even apparatus for rendering woven or printed patterns in textiles. For purposes of the discussion herein, such devices will be referred to collectively as rendering devices, i.e., any device used to render an image from a digital description of the image. Typically, rendering devices produce the image by scanning in "raster" fashion.
Color rendering devices typically employ three or four "process" colors. The process colors may be primary colors (Red, Blue and Green) as in a cathode-ray tube display, or may be complementary colors (Cyan, Magenta, Yellow and Black) as in an Oce Graphics Model G5232 Color Thermal Plotter. The full-color image to be rendered may, for example, be represented as a set of process-color images made up of an arrangement of individual pixels (in the case of a cathode-ray tube display) or of individual dots or of spots made up of a pattern of individual dots (in the case of printers or plotters). The set of process-color images, when overlaid and properly registered, produce a full-color output image. When viewed from a distance, the process-color pixels or dots or spots which form the image are spatially integrated by the human eye to give the perception of a wide range of hue and intensity.
A dot-size modulation rendering device is one which produces variable-sized dots representing a certain number of levels of color intensity, each dot represented by, e.g., two or three digital bits. An example of a dot-size modulation rendering device is the Iris 3024 color ink jet printer with up to 31 different sized dots. A binary rendering device, one which produces either a full-sized dot or no dot at all, represents each dot by a single digital bit ("dot-on" and "dot-off"). The Oce Graphics Model G5232 Color Thermal Plotter is an example of a binary rendering device. With either type of device, the limited number of available intensity levels may be insufficient for rendering an image with the desired range of intensity levels.
It is known that an expanded range of available intensities may be approximated with graphic output devices by use of dot patterns. FIG. 1a shows a simple example using a 2.times.2 pattern of "on"/"off" dots to approximate five intensity levels. In general, an n.times.n group of binary dots can provide n.sup.2 +1 intensity levels. Spatial resolution may thus be sacrificed to obtain increased intensity resolution.
Until recently, color rendering devices intended for such applications as color output of computer graphics have concentrated on obtaining merely more colors, rather than on the consistent rendering of exact colors. While such devices may be acceptable for rendering line-drawings from computer-aided drafting systems and the like, they are generally unable to faithfully reproduce colors in more complex images (such as digitized photographic images).
Many color rendering devices in current use in desktop publishing employ ordered dithering techniques for representing the output colors. One example of such a device is the Tektronix Phaser CPS color thermal printer. In general, ordered dithering techniques serve well to obtain a certain number of colors using three or four process colors, such as Green, Red and Blue, or Cyan, Magenta, Yellow and Black. Typically, a 5.times.5 square matrix of pixels or dots is used to approximate 25 intensities for any given color. But because sufficiently precise registration of the overlaid process color images is not always possible (such as when the process color images are sequentially applied to a sheet of paper), consistently accurate reproduction of color images is not assured. Even slight misalignment of the process-color images can result in moire patterns and/or other perceptible deficiencies in the rendered image. An advantage of ordered dithering techniques, and perhaps a major reason for their widespread use, is that they are compatible with the hardware requirements of binary digital processors; that is, they can accommodate the need to replicate binary patterns whose sizes are compatible with the processor--typically 8 -bit or 16-bit patterns.
Recent increased emphasis on accurate computer-based rendition of color images has led to interest in digital simulation of the halftoning techniques long used in the printing industry to obtain accurate colors in printing magazines, books, posters and the like. Digitally-simulated halftoning can overcome many of the problems inherent with ordered dithering techniques, and permit repeatable rendering of images with accurate color and intensity.
In the halftoning technique used in the printing industry, each tiny region of a monochrome image is imprinted with a circle of ink (e.g., black ink for black-and-white images) having an area proportional to the blackness (1-intensity) of the area in the original image. Newspaper halftones may, for example, use a frequency of 60 to 80 lines per inch, while magazine and advertising halftones use up to 150 lines per inch.
In conventional color halftoning as used in the printing industry, images of four process colors are overlaid to render the full-color output image. Rendered-color areas are thereby formed of rosette-like regions of juxtaposed or partially overlapping process-color dots. Each of the process-color images may be viewed as being like a window screen having parallel rows of openings (dots) with a specified distance between each of the openings.
If any two of the process-color images are overlaid at a small acute angle (less than about 15 degrees) between the rows of openings, color rendition suffers and moire patterns can appear in the rendered image with even slight misalignment of the process-color images. Therefore, in conventional color halftoning, the screens representing the individual process colors are rotated relative to one another at carefully-selected angles. That is, a first process-color image (for example, yellow) is printed, its screen orientation being at a reference angle such as 90 degrees relative to the image to be rendered. Then a second process-color image (for example, Magenta) is printed, its screen rotated at an angle such as 75 degrees from the reference angle. Then a third process-color image (for example, Cyan) is printed, its screen rotated at an angle such as 105 degrees from the reference angle. Finally the fourth process-color image (for example, Black) is printed, its screen rotated at an angle such as 45 degrees from the reference angle. Rotating screens at suitable angles offers independence from color drifting problems caused by slight errors in registration of the process-color images. Selection of the best angles to use for a given process or rendering device is generally a matter of experimentation.
The process of rendering continuous-tone images on a computer-based rendering device is referred to as digital halftoning. The goal is to generate the appearance of continuous toning by carefully defining the arrangement of pixels or dots. For any given digital halftone, there is some fixed number of tonal intensities, each of which is a pattern of pixels or dots. The pixels or dots of the pattern may be either binary or variable-sized, depending upon the capabilities of the particular rendering device. For multiple-color printers, a digital halftone image is generated for each process color. Further information about digital halftoning may be found in R. Ulichney, Digital Halftoning (1987), The MIT Press, Cambridge, Mass., the content of which is incorporated herein for all purposes by this reference.
While computer-based, digital simulation of full-color halftoning is a desirable objective, practical limitations have hindered its use. As with ordered dithering techniques, a separate bit-mapped image must be composed for each process color of the rendering device. The quantity of data to be processed for such composition is substantial: for example, an 8-inch by 10-inch color image to be rendered with a device having a resolution of 300 dots per inch and one bit per dot (such as an Oce Graphics Model G5232 Color Thermal Plotter) requires composition of four separate images each comprising 7.2 million bits. If the requirement of computing halftone screen patterns at four different angles and for multiple intensity levels within the image is added, substantial additional computing power is needed.
Rather than generating an entire simulated halftone screen for each process color of an image, a set of rectangular repeating patterns can be stored and retrieved for use in filling incremental regions of the image. These patterns can be considered as representing "tiles" to be used to construct a simulated halftone screen. The area of the "tile" may be selected arbitrarily, or as a function of computer hardware requirements. For reasons of hardware read/write efficiency and bit manipulation, these pattern tiles usually have dimensions which are a power of two (typically 8-by-8 or 16-by-16 dot locations) and are typically square. The pattern contained within the pattern tile is usually defined by an external computing process (e.g., an ordered dithering algorithm) or is predefined and selected by an external process (e.g., retrieved from memory). The pattern's dimensions are usually identical to those of the pattern tile. As with patterned wallpaper or floor tiles, these pattern tiles are used as a repeating pattern which is replicated at incremental regions throughout some fill area. Storage of such patterns can consume a large amount of memory. For example, a 32.times.32 bit pattern would require 32 long words (32 bits each) of storage for each pattern. If the image is to be rendered with four process colors each having 26 intensity levels, 104 minimal tiles must be defined and stored in memory, requiring approximately 13,312 8-bit bytes of memory.
Some current computer graphics chips allow for dynamic definition of a pattern tile for filling polygonal areas. The model DP8500 raster graphics processor, available from National Semiconductor Corporation, uses a set of 16 registers, each register being 16 bits wide, to define the pattern. Each register is used for a specific scan line, repeating horizontally to fill that line. Successive registers are used to fill successive scan lines; the pattern repeats after 16 scan lines. The processor is constructed such that the pattern tile must be 16.times.16. The NEC model 7200 computer graphics chip, which is no longer in production, is similar in operation to the National Semiconductor model DP8500 processor, is limited in size to a 16.times.16 pattern, and suffers from the same limitations. The HD63484 ACRTC advanced CRT controller, available from Hitachi, uses a 16.times.16 pattern RAM. The repeating pattern (and thus the pattern tile) may be defined to be any rectangular area within this pattern RAM, but is limited to a maximum size of 16.times.16. Its primary drawback, however, is its use of a seed fill algorithm to fill areas. The boundary of the fill area must first be drawn as an outline and then filled. It is also noted that these implementations are limited to binary patterns, and do not allow for multiple bits per dot or pixel.
Unfortunately, the repeating tiles which can be defined with current computer graphics chips are generally not well-suited for digital simulation of halftoning. Digital simulation of halftone screens uses a regular repeating pattern for each intensity level of the four process colors. These repeating patterns are sometimes also referred to as intensity tables. See, for example, J. Foley and A. VAN DAM, FUNDAMENTALS OF INTERACTIVE COMPUTER GRAPHICS (1983), Addison-Wesley Publishing Company, the content of which is incorporated herein by this reference for all purposes. A minimal area of the repeating pattern can be calculated for a given line resolution and halftone screen angle. This minimal area forms a "tile" which can be used to replicate the pattern within any polygonal area. However, the dimension of a side of these minimal tiles for common halftoning angles and line frequencies is usually not a power of two; it may be any integer number, depending upon the desired screen rotation angle. For example, the minimal tile for an angle of 34 degrees would require a 13.times.13 pattern, and the minimal tile for an angle of 53 degrees would require a 25.times. 25 repeating pattern. Defining a smaller repeating pattern (say 13.times.13) within the larger repeating tile (say 16.times.16) of current graphics processor chips would result in the incorrect replication of the repeating pattern throughout the fill area.
To illustrate, FIGS. 1b-1e show an example of a set of repeating patterns which might be used to obtain digital halftoning screens at rotation angles of 26, 33, 18 and 53 degrees, respectively. As can be seen, the halftone screens do not line up on power of 2 boundaries; that is, patterns of 5.times.5, 13.times.13 or 25.times.25 are required to produce simulated halftoning screens of the correct angles. However, the user is constrained by the binary nature of the graphics processor's internal structures to define the tiles as square areas whose dimension on one side is a power of two (e.g., 4.times.4, 8.times.8, 16.times.16, or 32.times.32). That is, for the pattern to be used as a tile in filling larger polygonal areas, the pattern is forced by the graphics processor's internal structures to repeat at one of those power of two boundaries. Where a pattern does not repeat at one of the power of two boundaries, the patterns of juxtaposed tiles will not match, resulting in perceptible horizontal and vertical " seams" in the rendered image. If a 5.times.5 repeating pattern is replicated within an 8.times.8 pattern tile, the patterns of adjacent tiles would be mismatched, resulting in visible "seams" in the rendered image.